package org.example.myleet.p628;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    /**
     * 63 ms
     * 讨论，讨论了很多复杂的情况，总体上是将数分为负数与非负数，并排序，再讨论
     * 这个其实可以简化很多，看Solution1
     */
    public int maximumProduct(int[] nums) {
        if (nums.length == 3) {
            //刚好3个数则直接返回，否则就是最少4个数
            return nums[0] * nums[1] * nums[2];
        }
        //非负数与负数
        List<Integer> nonNegativeNums = new ArrayList<>(nums.length);
        List<Integer> negativeNums = new ArrayList<>(nums.length);
        for (int n : nums) {
            if (n >= 0) {
                nonNegativeNums.add(n);
            } else {
                negativeNums.add(n);
            }
        }
        nonNegativeNums.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        negativeNums.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        int maxProduct;
        int nonNegSize = nonNegativeNums.size();
        int negSize = negativeNums.size();
        if (negativeNums.size() < 2) {
            //如果负数只有一个或没有，都不能使用负数，则使用最大的三个非负数
            maxProduct = nonNegativeNums.get(nonNegSize - 1) * nonNegativeNums.get(nonNegSize - 2) * nonNegativeNums.get(nonNegSize - 3);
        } else {
            if (nonNegSize < 1) {
                //如果非负数一个都没有，则只能使用最大都三个负数
                maxProduct = negativeNums.get(negSize - 1) * negativeNums.get(negSize - 2) * negativeNums.get(negSize - 3);
            } else if (nonNegSize < 3) {
                //如果非负数有1个或2个，则只能使用最小的两个负数再加一个最大的非负数
                maxProduct = negativeNums.get(0) * negativeNums.get(1) * nonNegativeNums.get(nonNegSize - 1);
            } else {
                //比较使用最小的两个负数再加一个最大的非负数，还是使用三个最大的非负数
                int tempNegProduct = negativeNums.get(0) * negativeNums.get(1);
                int tempNonNegProduct = nonNegativeNums.get(nonNegSize-1) * nonNegativeNums.get(nonNegSize-2);
                maxProduct = Math.max(tempNonNegProduct * nonNegativeNums.get(nonNegSize - 3), (tempNegProduct * nonNegativeNums.get(nonNegSize - 1)));
            }
        }
        return maxProduct;
    }
}
